package com.example.question.dp.dp2;

public class Code08_322_CoinChange {
    public static void main(String[] args) {
        int[] coins = new int[]{1, 2, 5};
        Code08_322_CoinChange change = new Code08_322_CoinChange();
        System.out.println("change.coinChange(coins,100) = " + change.coinChange(coins, 100));
    }


    private static int MAX = 100000;

    public int coinChange(int[] coins, int amount) {
        Integer[][] memo = new Integer[coins.length][amount + 1];
        return f3(coins, amount, 0, 0, memo);
    }

    /**
     * memo[i][j]表示在硬币数组的第i个位置开始，凑成金额j所需的最少硬币数。
     * 在每次计算前，我们先检查memo中是否已经保存了该结果，如果有，则直接返回，避免重复计算。
     * 如果没有，则进行递归计算，并将结果保存到memo中。
     * 通过这种记忆化搜索优化，可以显著减少重复计算，提高算法的执行效率。
     * 对于不同的硬币组合和金额，f0方法只会计算一次，并将结果存储在memo中，后续直接返回已计算的结果。
     */
    private int f0(int[] coins, int amount, int index) {
        if (amount < 0) {
            return -1;
        }

        if (amount == 0) {
            return 0;
        }
        int minCoins = MAX;
        for (int i = 0; i < coins.length; i++) {
            int res = f0(coins, amount - coins[i], i);
            if (res >= 0) {
                minCoins = Math.min(minCoins, res + 1);
            }
        }
        return minCoins;
    }

    /**
     * f2方法本身并不能直接进行记忆化搜索优化，因为它在每次递归调用中的count参数是累积的，而不是表示硬币数的中间结果。因此，无法简单地使用记忆化搜索来优化f2方法。
     */
    private int f2(int[] coins, int amount, int index, int count) {
        if (amount < 0) {
            return -1;
        }

        if (amount == 0) {
            return count;
        }
        int minCoins = MAX;
        for (int i = 0; i < coins.length; i++) {
            int res = f2(coins, amount, i, count + 1);
            if (res >= 0) {
                minCoins = Math.min(minCoins, res);
            }
        }
        return minCoins;
    }

    private int f3(int[] coins, int amount, int index, int count, Integer[][] memo) {
        if (amount < 0) {
            return -1;
        }

        if (amount == 0) {
            return count;
        }

        if (memo[index][amount] != null) {
            return memo[index][amount];
        }


        int minCoins = MAX;
        for (int i = 0; i < coins.length; i++) {
            int res = f3(coins, amount - coins[i], i, count + 1, memo);
            if (res >= 0) {
                minCoins = Math.min(minCoins, res);
            }
        }
        memo[index][amount] = minCoins != MAX ? minCoins : -1;
        return memo[index][amount];
    }
}
